//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组


package leetcode.d_1_99;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

//Java：柱状图中最大的矩形
public class P84LargestRectangleInHistogram{
    public static void main(String[] args) {
        P84LargestRectangleInHistogram solution = new P84LargestRectangleInHistogram();
        int[] heights = new int[]{2,1,5,6,2,3};
        System.out.println(solution.largestRectangleArea(heights)); // 10
        System.out.println(solution.largestRectangleArea2(heights)); // 10
    }


    // 单调增栈：
    // 进栈前弹出的都是左边比自己大的→确定左边界；
    // 出栈时必定是右边第一次遇到比自己小的→确定右边界
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] left = new int[n]; // 左边界默认是-1
        int[] right = new int[n];
        Arrays.fill(right, n); // 右边界默认是n

        // 使用单调栈，确定每个值的左右边界，即左右第一个比自己小的值
        Deque<Integer> stack = new ArrayDeque<>();
        for(int i=0; i<n; i++) {
            while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
                // 确定右边界，栈中的第一个索引遇到了第一个比自己小的值
                right[stack.peek()] = i;
                stack.pop();
            }
            // 确定左边界，当前索引遇到了左边第一个比自己小的值
            left[i] = stack.isEmpty()? -1 : stack.peek();
            stack.push(i);
        }

        int maxArea = 0;
        for(int i=0; i<n; i++) {
            maxArea = Math.max(maxArea, heights[i]*(right[i]-left[i]-1));
        }
        return maxArea;
    }

    // 暴力法
    public int largestRectangleArea2(int[] heights) {
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minHeight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minHeight = Math.min(minHeight, heights[j]);
                maxArea = Math.max(maxArea, minHeight * (j-i+1));
            }
        }
        return maxArea;
    }

}